FIG. 11 represents an information processing system in which a plurality of nodes (information processing apparatuses) 110 is connected to each other via a ring bus (RING) connecting the plurality of nodes to each other in an annular shape. Each node 110 includes a central processing unit (CPU) 111, a memory 112, a memory controller 113, and a crossbar unit (XB) 114. The CPU 111 performs an arithmetic processing and issues a request as well. According to the received request, the memory controller 113 performs a data writing or a data reading with respect to the memory 112. The crossbar unit (XB) 114 determines a reception destination of a packet such as the request transmitted via the ring bus RING, and controls the transmission of the packet.
The crossbar units (XB) 114 of the nodes are connected to each other in a ring shape, and each node 110 may access the memory 112 of an arbitrary node connected via the ring bus (RING). The crossbar unit (XB) 114 of each node 110 stores a request addressed to (=received by) another node in queues (buffers) Q11 and Q12 which are holding units, causes the request to be arbitrated in an arbitration unit 115, and transmits the request to another node of the next stage. Further, the crossbar unit (XB) 114 stores a request addressed to its own node in queues (buffers) Q21 and Q22, causes the request to be arbitrated in an arbitration unit 116, and transmits the request to the memory controller 113. In this manner, each node 110 receives and processes the request addressed to the own node, and transmits the request not addressed to the own node to another node of the next stage.
Here, in the information processing system having the plurality of nodes 110 connected to each other via the ring bus RING as illustrated in FIG. 11, when a node becomes a busy state and suppresses the reception of a request from a node of the previous stage, the requests are piled up in the node of the previous stage, and finally, a node of the stage next to the node that is the first to have become the busy state also becomes the busy state. As a result, a deadlock occurs.
For example, in a memory access request from the node A 110-A to the node C 110-C illustrated in FIG. 11, when the processing by the memory controller 113-C of the node C 110-C becomes slow and the node B 110-B becomes the busy state, a request of the node A 110-A from another node may not be issued as well. Further, when the node A 110-A becomes the busy state, a request of the node D 110-D from another node may not also be issued and the node D 110-D becomes the busy state so that the deadlock occurs. As described above, in the information processing system having the plurality of nodes 110 connected to each other via the ring bus (RING), the deadlock may occur due to the busy state of a node.
There has been suggested a technology which resolves the circumstance of the deadlock by storing a request in a memory, rather than in a queue, when the circumstance of the deadlock is detected (see, e.g., Japanese Laid-Open Patent Publication No. 2000-067023).